package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 224. 基本计算器
 * 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "1 + 1"
 * 输出：2
 * 示例 2：
 *
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 * 示例 3：
 *
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 3 * 105
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 * @author SHM
 */
public class CalculateI {
    public int calculate(String s) {
        Deque<Integer> dequeI = new LinkedList<>();
        Deque<Character> dequeC = new LinkedList<>();
        char[] cc = s.toCharArray();
        // int ans = 0;
        int operand = 0;

        for(char c:cc){
            if(Character.isDigit(c)){
                if(operand!=0){
                    dequeI.push(10*dequeI.pop()+(int)(c-'0'));
                }else{
                    dequeI.push((int)(c-'0'));
                }
                operand = dequeI.peek();
            }else if(c=='+'||c=='-'){
                operand = 0;
                if(!dequeC.isEmpty()&&dequeC.peek()!='('){
                    // while(!dequeC.isEmpty()){
                    char ch = dequeC.pop();
                    if(ch=='+'){
                        dequeI.push(dequeI.pop()+dequeI.pop());
                    }else if(ch=='-'){
                        dequeI.push(-dequeI.pop()+dequeI.pop());
                    }
                    // }
                }
                dequeC.push(c);
            }else if(c=='('){
                operand = 0;
                dequeC.push(c);
            }else if(c==')'){
                operand = 0;
                char ch = dequeC.pop();
                while(ch!='('){
                    if(ch=='+'){
                        dequeI.push(dequeI.pop()+dequeI.pop());
                    }else if(ch=='-'){
                        dequeI.push(-dequeI.pop()+dequeI.pop());
                    }
                    ch = dequeC.pop();
                }
            }else{
                operand=0;
            }
        }

        while(!dequeC.isEmpty()){
            char ch = dequeC.pop();
            if(ch=='+'){
                dequeI.push(dequeI.pop()+dequeI.pop());
            }else if(ch=='-'){
                dequeI.push(-dequeI.pop()+dequeI.pop());
            }
        }

        return dequeI.peek();
    }

    /**
     * 概述
     * 解决这个问题需要理解以下内容：
     *
     * 输入始终包含有效的字符串。
     * 加减法规则。
     * 括号中的优先含义。
     * 空格不影响输入表达式的计算。
     * 方法二：栈和不反转字符串
     * 解决 - 结合律的问题的一个分厂简单的方法就是使将 - 运算符看作右侧操作数的大小。一旦我们将 - 看作操作数的大小，则表达式将只剩下一个操作符。就是 + 运算符，而 + 是遵循结合律的。
     *
     * 例如，A-B-CA−B−C 等于 A + (-B) + (-C)A+(−B)+(−C)。
     *
     * 重写以后的表达式将遵循结合律，所以我们从左或从右计算表达式都是正确的。
     *
     * 我们需要注意的是给定的表达式会很复杂，即会有嵌套在其他表达式的表达式。即 (A - (B - C))，我们需要 B-C 外面的 - 号与 B-C 关联起来，而不是仅仅与 B 关联起来。
     *
     * / 我们可以通过遵循前面的基本练习并将符号与其右侧的表达式关联来解决此问题。然而，我们将采用的方法有一个小的转折，因为我们将在运行中评估大多数表达式。这减少了推送和弹出操作的数量。
     *
     * 算法：
     *
     * 正序迭代字符串。
     * 操作数可以由多个字符组成，字符串 "123" 表示数字 123，它可以被构造为：123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字，则我们要将先前形成的操作数乘以 10 并于读取的数字相加，形成操作数。
     * 每当我们遇到 + 或 - 运算符时，我们首先将表达式求值到左边，然后将正负符号保存到下一次求值。
     * 如果字符是左括号 (，我们将迄今为止计算的结果和符号添加到栈上，然后重新开始进行计算，就像计算一个新的表达式一样。
     * 如果字符是右括号 )，则首先计算左侧的表达式。则产生的结果就是刚刚结束的子表达式的结果。如果栈顶部有符号，则将此结果与符号相乘。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 指的是字符串的长度。这种方法与前一种方法的区别在于，这种方法的每个字符都将被精确的处理一次。但是前面的方法中，每个字符可能被处理两次，一次是被添加到栈上，另一次是被弹出处理最终结果。这就是为什么这种方法更快的原因。
     * 空间复杂度：O(N)O(N)，其中 NN 指的是字符串的长度。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode/
     * @param s
     * @return
     */
    public int calculate_2(String s) {
        Deque<Integer> dequeI = new LinkedList<>();
        char[] cc = s.toCharArray();
        int operand = 0;
        int ans = 0;
        int sign = 1;
        for (char c : cc) {
            if(Character.isDigit(c)){
                operand = operand*10+(int)(c-'0');
            }else if(c=='+'){
                ans+=sign*operand;
                sign=1;
                operand=0;
            }else if(c=='-'){
                ans+=sign*operand;
                sign=-1;
                operand=0;
            }else if(c=='('){
                dequeI.push(ans);
                dequeI.push(sign);
                sign = 1;
                ans = 0;
            }else if(c==')'){
                ans+=sign*operand;
                ans*=dequeI.pop();
                ans+=dequeI.pop();
                operand = 0;
            }
        }
        return ans+(sign*operand);
    }
}
